package 二分算法;

import java.util.*;

/**
 * https://leetcode.cn/problems/group-anagrams/description/
 * 字母异位词分组
 */
public class likou49 {

    // 更加简单的写法
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
        // 1. 先把异位词进行分组
        for(String str : strs){
            char[] ch = str.toCharArray();
            // 字符数组进行排序
            Arrays.sort(ch);
            String key = new String(ch);

            // 进入哈希表之前, 先进行判断
            if(!hash.containsKey(key)){
                hash.put(key, new ArrayList<>());
            }
            hash.get(key).add(str);
        }
        // 从哈希表中收集结果
        return new ArrayList<>(hash.values());
    }

    public List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
        // 1. 先把异位词进行分组
        for(String str : strs){
            char[] ch = str.toCharArray();
            // 字符数组进行排序
            Arrays.sort(ch);
            String key = new String(ch);

            // 进入哈希表之前, 先进行判断
            if(!hash.containsKey(key)){
                List<String> list = new ArrayList<>();
                list.add(str);
                hash.put(key, list);
            }
            hash.get(key).add(str);
        }
        // 从哈希表中收集结果
        List<List<String>> ret = new ArrayList<>();
        for (List<String> value : hash.values()) {
            ret.add(value);
        }
        return ret;
    }

}
